package cn.arts.assumejson.algo.sort.class01;

/**
 * <a href="https://leetcode.cn/problems/find-peak-element/">find-peak-element</a>
 *
 * @author by <a href="mailto:ligang941012@gmail.com">gang.Li</a>
 * @since 2024/7/29 0:49
 */
public class FindPeakElementFromLC162 {
    // Use a dichotomy
    public static int findPeakElement(int[] arr) {
        if (arr == null || arr.length < 1) return -1;
        if (arr.length == 1 || arr[0] > arr[1]) return 0;
        if (arr[arr.length - 1] > arr[arr.length - 2]) return arr.length - 1;

        int L = 1, mid, R = arr.length - 2;
        while (L < R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
                return mid;
            } else {
                // 需要保持向上的趋势
                if (arr[mid] > arr[mid - 1]) {
                    L = mid + 1;
                } else {
                    R = mid - 1;
                }
            }
        }
        return arr[R] > arr[L] ? R : L;
    }
}
